package listbyorder.access101_200.test133;

import java.util.*;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/11 10:01
 */
public class Solution2 {

    // 方法二： BFS一次遍历搞定
    public Node cloneGraph(Node node) {
        if (node == null) return node;

        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        Map<Integer, Node> map = new HashMap<>();
        Node root = new Node();
        root.val = node.val;
        root.neighbors = new ArrayList<Node>();
        map.put(node.val, root);

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            for (Node neighbor : cur.neighbors) {
                if (!map.containsKey(neighbor.val)) {
                    Node n = new Node();
                    n.val = neighbor.val;
                    n.neighbors = new ArrayList<>();
                    map.put(neighbor.val, n);
                    queue.add(neighbor);
                }
                map.get(cur.val).neighbors.add(map.get(neighbor.val));
            }
        }

        return map.get(node.val);
    }
}
